home *** CD-ROM | disk | FTP | other *** search
/ The PC-SIG Library 10 / The PC-Sig Library - Shareware for the IBM PC and Compatibles (PC-SIG)(Tenth Edition Disks 1-2804)(1991).iso / PC_SIGCD / 22 / 4 / DISK2247.ZIP / CBASE101.ZIP / BTREE101.ZIP / BTINSERT.C < prev    next >
Text File  |  1990-06-20  |  9KB  |  393 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)btinsert.c    1.4 - 90/06/20" */
  5.  
  6. #include <blkio.h>
  7. #include <bool.h>
  8. #include <errno.h>
  9. /*#include <stddef.h>*/
  10. /*#include <stdlib.h>*/
  11. /*#include <string.h>*/
  12.  
  13. /* local headers */
  14. #include "btree_.h"
  15.  
  16. /* FREE:  free all allocated storage */
  17. #define FREE {                                \
  18.     terrno = errno;                            \
  19.     bt_ndfree(btnp);                        \
  20.     btnp = NULL;                            \
  21.     bt_ndfree(lbtnp);                        \
  22.     lbtnp = NULL;                            \
  23.     bt_ndfree(pbtnp);                        \
  24.     pbtnp = NULL;                            \
  25.     bt_ndfree(rbtnp);                        \
  26.     rbtnp = NULL;                            \
  27.     free(bttpl.keyp);                        \
  28.     bttpl.keyp = NULL;                        \
  29.     errno = terrno;                            \
  30. }
  31.  
  32. static int setcursor(btp, lbtnp, rbtnp)
  33. btree_t *btp;
  34. btnode_t *lbtnp;
  35. btnode_t *rbtnp;
  36. {
  37.     if (btp->sp[0].key <= lbtnp->n) {
  38.         if (bt_ndcopy(btp, btp->cbtnp, lbtnp) == -1) {
  39.             BTEPRINT;
  40.             return -1;
  41.         }
  42.         btp->cbtpos.node = btp->sp[0].node;
  43.         btp->cbtpos.key = btp->sp[0].key;
  44.     } else {
  45.         if (bt_ndcopy(btp, btp->cbtnp, rbtnp) == -1) {
  46.             BTEPRINT;
  47.             return -1;
  48.         }
  49.         btp->cbtpos.node = lbtnp->rsib;
  50.         btp->cbtpos.key = btp->sp[0].key - lbtnp->n;
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
  56. /*man---------------------------------------------------------------------------
  57. NAME
  58.      btinsert - btree insert
  59.  
  60. SYNOPSIS
  61.      #include <btree.h>
  62.  
  63.      int btinsert(btp, buf)
  64.      btree_t *btp;
  65.      const void *buf;
  66.  
  67. DESCRIPTION
  68.      The btinsert function inserts the key pointed to by buf into
  69.      btree btp.  The cursor is positioned to the inserted key.  If the
  70.      insertion fails, the position of the cursor is undefined.  buf
  71.      must point to a storage area as large as the key size for the
  72.      specified btree.
  73.  
  74.      btinsert will fail if one or more of the following is true:
  75.  
  76.      [EINVAL]       btp is not a valid btree pointer.
  77.      [EINVAL]       buf is the NULL pointer.
  78.      [BTEDUP]       The key at buf is already in btree btp.
  79.      [BTELOCK]      btp is not write locked.
  80.      [BTENOPEN]     btp is not open.
  81.  
  82. SEE ALSO
  83.      btdelete, btsearch.
  84.  
  85. DIAGNOSTICS
  86.      Upon successful completion, a value of 0 is returned.  Otherwise,
  87.      a value of -1 is returned, and errno set to indicate the error.
  88.  
  89. ------------------------------------------------------------------------------*/
  90. int btinsert(btp, buf)
  91. btree_t *btp;
  92. const void *buf;
  93. {
  94.     btnode_t *    btnp    = NULL;        /* node receiving new key */
  95.     bttpl_t        bttpl;            /* btree tuple */
  96.     bool        err    = FALSE;    /* error flag */
  97.     int        found    = 0;        /* key found flag */
  98.     bool        grow    = FALSE;    /* tree grow flag */
  99.     btnode_t *    lbtnp    = NULL;        /* left sibling node */
  100.     bpos_t        lsib    = NIL;        /* lsib location */
  101.     bpos_t        node    = NIL;        /* node location */
  102.     btnode_t *    pbtnp    = NULL;        /* parent node */
  103.     int        pkn    = 0;        /* parent key number */
  104.     bpos_t        pnode    = 0;        /* parent node location */
  105.     btnode_t *    rbtnp    = NULL;        /* right sibling node */
  106.     bpos_t        rsib    = NIL;        /* rsib location */
  107.     unsigned long    spi    = 0;        /* search path index */
  108.     int        terrno    = 0;        /* tmp errno */
  109.     int        total    = 0;        /* total keys in node and sib */
  110.  
  111.     /* initialize automatic aggregates */
  112.     memset(&bttpl, 0, sizeof(bttpl));
  113.  
  114.     /* validate arguments */
  115.     if (!bt_valid(btp) || buf == NULL) {
  116.         errno = EINVAL;
  117.         return -1;
  118.     }
  119.  
  120.     /* check if not open */
  121.     if (!(btp->flags & BTOPEN)) {
  122.         errno = BTENOPEN;
  123.         return -1;
  124.     }
  125.  
  126.     /* check lock */
  127.     if (!(btp->flags & BTWRLCK)) {
  128.         errno = BTELOCK;
  129.         return -1;
  130.     }
  131.  
  132.     /* locate position for key and generate search path */
  133.     found = bt_search(btp, buf);
  134.     if (found == -1) {
  135.         BTEPRINT;
  136.         return -1;
  137.     }
  138.     if (found == 1) {            /* check for duplicate key */
  139.         errno = BTEDUP;
  140.         return -1;
  141.     }
  142.  
  143.     /* create working nodes */
  144.     btnp = bt_ndalloc(btp);
  145.     if (btnp == NULL) {
  146.         BTEPRINT;
  147.         return -1;
  148.     }
  149.     lbtnp = bt_ndalloc(btp);    /* left sibling */
  150.     if (lbtnp == NULL) {
  151.         BTEPRINT;
  152.         FREE;
  153.         return -1;
  154.     }
  155.     rbtnp = bt_ndalloc(btp);    /* right sibling */
  156.     if (rbtnp == NULL) {
  157.         BTEPRINT;
  158.         FREE;
  159.         return -1;
  160.     }
  161.     pbtnp = bt_ndalloc(btp);    /* parent */
  162.     if (pbtnp == NULL) {
  163.         BTEPRINT;
  164.         FREE;
  165.         return -1;
  166.     }
  167.  
  168.     /* initialize btnp with current node */
  169.     if (bt_ndcopy(btp, btnp, btp->cbtnp) == -1) {
  170.         BTEPRINT;
  171.         FREE;
  172.         return -1;
  173.     }
  174.  
  175.     /* initialize bttpl with key to insert */
  176.     bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
  177.     if (bttpl.keyp == NULL) {
  178.         BTEPRINT;
  179.         FREE;
  180.         errno = ENOMEM;
  181.         return -1;
  182.     }
  183.     memcpy(bttpl.keyp, buf, btp->bthdr.keysize);
  184.     bttpl.child = NIL;
  185.  
  186.     /* set modify bit in in-core header and write to file */
  187.     btp->bthdr.flags |= BTHMOD;
  188.     if (bputhf(btp->bp, sizeof(bpos_t),
  189.                 (char *)&btp->bthdr + sizeof(bpos_t),
  190.                 sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
  191.         BTEPRINT;
  192.         FREE;
  193.         return -1;
  194.     }
  195.     if (bsync(btp->bp) == -1) {
  196.         BTEPRINT;
  197.         FREE;
  198.         return -1;
  199.     }
  200.  
  201.     if (btp->bthdr.height == 0) {
  202.         grow = TRUE;
  203.     }
  204.  
  205.     /* loop from leaf node to root */
  206.     for (spi = 0; spi < btp->bthdr.height; ++spi) {
  207.         /* insert new key into node */
  208.         if (bt_ndinskey(btp, btnp, btp->sp[spi].key, &bttpl) == -1) {
  209.             BTEPRINT;
  210.             err = TRUE;
  211.             break;
  212.         }
  213.  
  214.         /* write to disk if node not too big */
  215.         if (btnp->n <= bt_ndmax(btp)) {
  216.             if (bt_ndput(btp, btp->sp[spi].node, btnp) == -1) {
  217.                 BTEPRINT;
  218.                 err = TRUE;
  219.                 break;
  220.             }
  221.             if (spi == 0) {        /* set cursor */
  222.                 if (bt_ndcopy(btp, btp->cbtnp, btnp) == -1) {
  223.                     BTEPRINT;
  224.                     err = TRUE;
  225.                     break;
  226.                 }
  227.                 btp->cbtpos.node = btp->sp[0].node;
  228.                 btp->cbtpos.key = btp->sp[0].key;
  229.             }
  230.             break;
  231.         }
  232.  
  233.         /* check if root */
  234.         if (spi == btp->bthdr.height - 1) {
  235.             if (bt_ndsplit(btp, btp->sp[spi].node, btnp, rbtnp, &bttpl) == -1) {
  236.                 BTEPRINT;
  237.                 err = TRUE;
  238.                 break;
  239.             }
  240.             if (spi == 0) {        /* set cursor */
  241.                 if (setcursor(btp, btnp, rbtnp) == -1) {
  242.                     BTEPRINT;
  243.                     err = TRUE;
  244.                     break;
  245.                 }
  246.             }
  247.             grow = TRUE;
  248.             break;
  249.         }
  250.  
  251.         /* try to shift keys with siblings */
  252.         /* read in parent node */
  253.         if (bt_ndget(btp, btp->sp[spi + 1].node, pbtnp) == -1) {
  254.             BTEPRINT;
  255.             err = TRUE;
  256.             break;
  257.         }
  258.         /* get locations of nodes */
  259.         node = btp->sp[spi].node;
  260.         pnode = btp->sp[spi + 1].node;
  261.         pkn = btp->sp[spi + 1].key - 1;
  262.         if (pkn == 0) {
  263.             lsib = NIL;
  264.         } else {
  265.             lsib = btnp->lsib;
  266.         }
  267.         if (pkn == pbtnp->n) {
  268.             rsib = NIL;
  269.         } else {
  270.             rsib = btnp->rsib;
  271.         }
  272.  
  273.         /* try shifting keys with right sibling */
  274.         if (rsib != NIL) {
  275.             if (bt_ndget(btp, rsib, rbtnp) == -1) {
  276.                 BTEPRINT;
  277.                 err = TRUE;
  278.                 break;
  279.             }
  280.             total = btnp->n + rbtnp->n;
  281.             if (total <= 2 * bt_ndmax(btp)) {
  282.                 if (bt_ndshift(btp, btnp, rbtnp, pbtnp, pkn + 1, pnode) == -1) {
  283.                     BTEPRINT;
  284.                     err = TRUE;
  285.                     break;
  286.                 }
  287.                 if (spi == 0) {        /* set cursor */
  288.                     if (setcursor(btp, btnp, rbtnp) == -1) {
  289.                         BTEPRINT;
  290.                         err = TRUE;
  291.                         break;
  292.                     }
  293.                 }
  294.                 break;
  295.             }
  296.         }
  297.  
  298.         /* try shifting keys with left sibling */
  299.         if (lsib != NIL) {
  300.             if (bt_ndget(btp, lsib, lbtnp) == -1) {
  301.                 BTEPRINT;
  302.                 err = TRUE;
  303.                 break;
  304.             }
  305.             total = lbtnp->n + btnp->n;
  306.             if (total <= 2 * bt_ndmax(btp)) {
  307.                 btp->sp[spi].key = lbtnp->n + btp->sp[spi].key;
  308.                 if (bt_ndshift(btp, lbtnp, btnp, pbtnp, pkn, pnode) == -1) {
  309.                     BTEPRINT;
  310.                     err = TRUE;
  311.                     break;
  312.                 }
  313.                 if (spi == 0) {        /* set cursor */
  314.                     if (setcursor(btp, lbtnp, btnp) == -1) {
  315.                         BTEPRINT;
  316.                         err = TRUE;
  317.                         break;
  318.                     }
  319.                 }
  320.                 break;
  321.             }
  322.         }
  323.  
  324.         /* split node */
  325.         if (bt_ndsplit(btp, node, btnp, rbtnp, &bttpl) == -1) {
  326.             BTEPRINT;
  327.             err = TRUE;
  328.             break;
  329.         }
  330.         if (spi == 0) {        /* set cursor */
  331.             if (setcursor(btp, btnp, rbtnp) == -1) {
  332.                 BTEPRINT;
  333.                 err = TRUE;
  334.                 break;
  335.             }
  336.         }
  337.  
  338.         /* bttpl must be inserted in pbtnp */
  339.         if (bt_ndcopy(btp, btnp, pbtnp) == -1) {
  340.             BTEPRINT;
  341.             err = TRUE;
  342.             break;
  343.         }
  344.     }
  345.     if (err) {
  346.         BTEPRINT;
  347.         FREE;
  348.         return -1;
  349.     }
  350.     bt_ndfree(btnp);    /* free in-core nodes */
  351.     bt_ndfree(lbtnp);
  352.     bt_ndfree(rbtnp);
  353.     bt_ndfree(pbtnp);
  354.  
  355.     /* check if the tree grew */
  356.     if (grow) {
  357.         if (bt_grow(btp, &bttpl) == -1) {
  358.             BTEPRINT;
  359.             free(bttpl.keyp);
  360.             return -1;
  361.         }
  362.         if (btp->bthdr.height == 1) {        /* set cursor */
  363.             if (bt_ndget(btp, btp->bthdr.root, btp->cbtnp) == -1) {
  364.                 BTEPRINT;
  365.                 free(bttpl.keyp);
  366.                 return -1;
  367.             }
  368.             btp->cbtpos.node = btp->bthdr.root;
  369.             btp->cbtpos.key = 1;
  370.         }
  371.     }
  372.     free(bttpl.keyp);
  373.  
  374.     /* increment key count */
  375.     btp->bthdr.keycnt++;
  376.  
  377.     /* clear modify bit in in-core header and write to file */
  378.     btp->bthdr.flags &= ~BTHMOD;
  379.     if (bputhf(btp->bp, sizeof(bpos_t),
  380.                 (char *)&btp->bthdr + sizeof(bpos_t),
  381.                 sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
  382.         BTEPRINT;
  383.         return -1;
  384.     }
  385.     if (bsync(btp->bp) == -1) {
  386.         BTEPRINT;
  387.         return -1;
  388.     }
  389.  
  390.     errno = 0;
  391.     return 0;
  392. }
  393.